package leetCode.sample;

import org.junit.Test;

public class SearchSolution {

    @Test
    public void test() {

        System.out.println(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 0));
        System.out.println(search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3));
        System.out.println(search(new int[]{4, 5, 6, 7, 8, 1, 2, 3}, 8));
    }


    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        return searchInner(nums, target, 0, nums.length - 1);
    }

    private int searchInner(int[] nums, int target, int left, int right) {
        int middle = (left + right) / 2;
        if (nums[middle] == target) {
            return middle;
        }
        if (nums[left] == target) {
            return left;
        }
        if (nums[right] == target) {
            return right;
        }
        if (left == right) {
            return -1;
        }
        if (nums[middle] > target) {
            if (nums[middle] > nums[left] && nums[left] < target) {
                return searchInner(nums, target, left, middle);
                // 解一定在左边或者不存在
            }
        } else if (nums[middle] < target) {
            if (nums[middle] < nums[right] && nums[right] > target) {
                return searchInner(nums, target, middle + 1, right);
                // 解一定在右边或者不存在
            }
        }
        int index = -1;
        index = searchInner(nums, target, left, middle);
        if (index > -1) {
            return index;
        }
        index = searchInner(nums, target, middle + 1, right);
        return index;
    }
}
